The present invention is directed to a method and apparatus for drawing computer generated lines using Bresenham's line drawing algorithm. More particularly, the present invention is directed to a method and apparatus for drawing lines using single (or multiple) instruction multiple data processors known as SIMD's (or MIMD'S) respectively.
In a SIMD processor, multiple tasks may operate on multiple data sets, while each task shares a single instruction set. A SIMD processor capable of operating on N data sets may generally function N times faster than a single processor if the same program is being used to operate on each of the N data sets. Accordingly, the performance of the SIMD may be optimized if each of the N tasks uses the same algorithm or instruction sequence. A SIMD processor differs from a multiple instruction multiple data processor ("MIMD") in that an MIMD is capable of operating on multiple data sets while using separate or distinct instruction sequences.
One type of algorithm which may be applied to multi-tasking processors is Bresenham's line drawing algorithm. Since computer generated lines are limited to representations based on discrete pixel locations, it often happens that the mathematical location of a point will differ from the location of the point on the screen. Bresenham's algorithm is directed towards this problem and is used for choosing pixel locations which tend to minimize differences between an actual mathematical line and a computer generated representation of such a line. Based on its determination of the error by which a drawn point on a line will deviate from the actual mathematical position of the point, Bresenham's algorithm will determine whether the next drawn point should be the one directly to the right of or one above and to the right of the last drawn point. In determining the error for any particular point, Bresenham's algorithm uses a composite error figure which has been incremented or decremented with each preceding point. The basic Bresenham algorithm to draw a line from (X.sub.1, Y.sub.1,) to (X.sub.2, Y.sub.2) can be described as shown in Table I below:
TABLE I ______________________________________ 1 dx = x.sub.2 -x.sub.1 2 dy = y.sub.2 -y.sub.1 3 inc1 = 2 * dy 4 inc2 = 2 * (dy-dx) 5 e = 2*dy - dx 6 x = x.sub.1 7 y = y.sub.1 8 for dx times { 9 draw point at x, y 10 if (e &lt; o) 11 e = e + inc1 12 else 13 e = e + inc2 14 y = y + 1 15 x = x + 1 { ______________________________________
A mathematical analysis of Bresenham's Algorithm can be found in "Fundamentals of Interactive Computer Graphics", by Foley and VanDam.
For a multi-tasking processor capable of operating on N data sets, a typical application of Bresenham's algorithm might involve using a separate task to draw each (1/N)th of the line. A SIMD processor could be employed using this method, as each of the N tasks could be made to use the same instruction sequence.
This method is illustrated in FIG. 1, where the line to be drawn (10) is divided into N segments labelled 10a, 10b, . . . 10n. Each of the N processors is used to draw one of these N segments, by first calculating the position of the first point of its respective segment, and thereafter by calculating successive points on its respective segment using, for example, Bresenham's algorithm.
The drawback in using the method shown in FIG. 1 to draw lines using a SIMD or MIMD processor, is that the optimal speed is not achieved. The loss of speed is attributable to the memory addressing mode which must be used to write and store the calculated points in the computer memory.
Computer memory chips are typically divided into sections called pages. Since, in the method shown in FIG. 1, the N points being calculated at any particular time are each separated by a distance equal to (1/N)th of the line, the N points are not contiguous and will therefore not typically be written onto the same page in memory. The fact that each of the N processors must write to a difference page in memory works to significantly slow the line generating process of FIG. 1.
In a different mode known as "page mode", memory writes are not made to multiple pages but instead only to a single page at a time. Writing to memory in page mode is significantly faster than writing to separate pages in memory.
It is an object of the present invention to make optimal use of SIMD architecture by operating on multiple data sets using the same instruction sequence.
It is a further object of the present invention to use SIMD architecture in a manner which capitalizes on the speed achievable by writing to memory in page mode.